package com.huawei.M01.iterator;

public class MaxIndex {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum;
        while (left < right) {
            int mid = (left + right - 1) / 2;
            if (valid(mid, n, index, maxSum)) { // 使用二分法边界的判断
                left = mid;
            } else {
                right = mid -1;
            }
        }
        return 0;
    }

    public boolean valid(int mid, int n, int index, int maxSum) {
        int right = n - index - 1;
        return mid + val(mid, index) + val(mid, right) <= maxSum;
    }

    private long val(int big, int length) {
        if (length + 1 <= big) {
            int small = big - length;
            return (long) (small + big - 1) * length / 2;
        } else {
            int ones = length - (big - 1);
            return (long) (big - 1) * big / 2 + ones;
        }
    }
}
